import java.awt.*;

public class CycleArray<T> {
    private T[] array;
    private int start;
    private int end;
    private int count;
    private int size;

    public CycleArray() {
        this(1);
    }

    @SuppressWarnings("unchecked")
    public CycleArray(int size) {
        this.size = size;
        this.array = (T[]) new Object[size];
        // strat指向第一个有效元素的索引，闭区间
        this.start = 0;
        // 切记 end是一个闭标签，即指向最后一个有效元素的下一个位置
        this.end = 0;
        this.count = 0;
    }

    // 自动扩缩容方法
    @SuppressWarnings("unchecked")
    public void resize(int newSize) {
        // 创建一个新数组
        T[] newArray = (T[]) new Object[newSize];
        // 拷贝数据
        for (int i = 0; i < count; i++) {
            newArray[i] = array[(start + i) % size];
        }
        array = newArray;
        // 重置start和end指针
        start = 0;
        end = count;
        size = newSize;
    }

    // 在数组头部添加元素，时间复杂度O(1)
    public void addFirst(T t) {
        // 当数组满容时，扩容为2倍
        if (count == size) {
            resize(size * 2);
        }
        // 因为start是闭区间，所以先左移后赋值
        start = (start - 1 + size) % size;
        array[start] = t;
        count++;
    }

    // 删除数组头部元素，时间复杂度O(1)
    public void removeFirst() {
        if (count == 0) {
            throw new RuntimeException("数组为空");
        }
        //  因为start是闭区间，所以先赋值后右移
        array[start] = null;
        start = (start + 1) % size;
        count--;
        // 如果数组元素减少到size / 4, 则缩小为size / 2
        if (count < size / 4) {
            resize(size / 2);
        }
    }

    // 在数组尾部添加元素，时间复杂度为O(1)
    public void addLast(T t) {
        if (count == size) {
            resize(size * 2);
        }
        // 因为end是开区间，所以先赋值后右移
        array[end] = t;
        end = (end + 1) % size;
        count++;
    }

    // 删除数组尾部元素，时间复杂度为O(1)
    public void removeLast() {
        if (count == 0) {
            throw new IllegalComponentStateException("数组为空");
        }
        // 因为end是开区间，所以先左移后赋值
        end = (end - 1 + size) % size;
        array[end] = null;
        count--;
        // 如果数组元素减少到size / 4, 则缩小为size / 2
        if (count < size / 4) {
            resize(size / 2);
        }
    }

    // 获取数组头部元素，时间复杂度为O(1)
    public T getFirst() {
        if (count == 0) {
            throw new RuntimeException("数组为空");
        }
        return array[start];
    }

    // 获取数组尾部元素，时间复杂度为O(1)
    public T getLast() {
        if (count == 0) {
            throw new RuntimeException("数组为空");
        }
        // end是开区间，指向的是最后一个元素的下一个位置
        return array[(end - 1 + size) % size];
    }

    public static void main(String[] args) {

    }
}
